package com.example.algorithm.greedy;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。
 *  请你以字符串形式返回这个最小的数字。
 *
 *  示例 1 ：
 * 输入：num = "1432219", k = 3
 * 输出："1219"
 * 解释：移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。
 *
 *  示例 2 ：
 * 输入：num = "10200", k = 1
 * 输出："200"
 * 解释：移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。
 *
 *  示例 3 ：
 * 输入：num = "10", k = 2
 * 输出："0"
 * 解释：从原数字移除所有的数字，剩余为空就是 0 。
 */
public class Leetcode402_RemoveKdigits {
    public static void main(String[] args) {
        String str = "1432219";
        int k = 3;

        str = "10200";
        k = 1;

        str = "2461";
        k = 1;

//        str = "10";
//        k = 1;
        System.out.println(new Solution().removeKdigits(str, k));
    }

    static class Solution {
        /**
         * 解法二:单调栈
         *
         * 考虑从左往右增量的构造最后的答案。
         * 我们可以用一个栈维护当前的答案序列，栈中的元素代表截止到当前位置，删除不超过 k 次个数字后，所能得到的最小整数。
         * 在使用 k 个删除次数之前，栈中的序列从栈底到栈顶单调不降。
         *
         * 因此，对于每个数字，如果该数字小于栈顶元素，我们就不断地弹出栈顶元素，直到
         * 栈为空
         * 或者新的栈顶元素不大于当前数字
         * 或者我们已经删除了 k 位数字
         *
         * 最后:
         *   如果我们删除了 m 个数字且 m<k，这种情况下我们需要从序列尾部删除额外的 k−m 个数字。
         *   如果最终的数字序列存在前导零，我们要删去前导零。
         *   如果最终数字序列为空，我们应该返回 00。
         *
         *
         * @param num
         * @param k
         * @return
         */
        private String removeKdigits2(String num, int k) {
            if (k >= num.length()) return "0";

            Deque<Character> deque = new LinkedList<>();
            char[] chars = num.toCharArray();
            // 使用单调栈使得越前面的元素尽可能的小
            for (int i = 0; i < chars.length; i++) {

                while (!deque.isEmpty() && k > 0 && deque.peekLast() > chars[i]) {
                    deque.pollLast();
                    k--;
                }

                deque.offerLast(chars[i]);
            }

            // 遍历完了字符串，并且栈里面已经全是单调递增了,但是k还没到0
            for (int i = 0; i < k; i++) {
                deque.pollLast();
            }

            StringBuilder sb = new StringBuilder();

            // 前导'0'的处理
            while (!deque.isEmpty()) {
                char c = deque.peekFirst();
                if (c == '0') {
                    deque.pollFirst();
                } else {
                    break;
                }
            }

            while (!deque.isEmpty()) { // 从前向后依次出队得到结果
                sb.append(deque.pollFirst());
            }
            return sb.length() == 0 ? "0" : sb.toString();
        }

        /**
         * 解法一:暴力法(贪心策略)
         * 若要使得剩下的数字最小，需要保证靠前的数字尽可能小。
         *
         * 从左往右找到第一个位置 i（i>0）使得 str[i]<str[i-1]并删去 str[i−1]
         * 如果不存在，说明整个数字序列单调不降，删去最后一个数字即可。
         * 重复k次即可
         *
         * @param num
         * @param k
         * @return
         */
        private String removeKdigits1(String num, int k) {
            if (k >= num.length()) return "0";

            StringBuilder sb = new StringBuilder(num);
            for (int i = 0; i < k; i++) {
                remove(sb);
            }
            System.out.println("xxx:" + sb.toString());
            // 去掉前导0
            while (true) {
                if (sb.length() > 1 && sb.charAt(0) == '0') {
                    sb.replace(0, 1, "");
                } else {
                    break;
                }
            }
            return sb.toString();
        }

        private void remove(StringBuilder sb) {
            for (int i = 1; i < sb.length(); i++) {
                if (sb.charAt(i) < sb.charAt(i - 1)) {
                    sb.replace( i - 1, i, "");
                    return;
                }
            }
            sb.replace(sb.length() - 1, sb.length(), "");
        }

        public String removeKdigits(String num, int k) {
            return removeKdigits2(num, k);
        }
    }
}
